c(d,k) = (n^k-1) / (n^d-1). Např. systém G(2,6) získává (dědí) vnořené systémy G(2,1), G(2,2) a G(2,3);
G(2,1) je také vnořený do G(2,2) a G(2,3).
V tomto textu je představena algebraická teorie souzvukových druhů. Každé uskupení tónů je zobrazeno jako instance takzvaného G-systému. Cílem je opatřit jednoduchý algoritmus pro generování hudebních struktur. Mohl by být užitečný pro programátory zabývající se počítačovou hudbou nebo analýzou hudby. Teorie G-systemů dává některé známé matematické výsledky jednoduchým a jasně uspořádaným způsobem. Proto by mohla být inspirující pro matematiky studující metody enumerací, teorii grup, algebraická řešení kombinatorických problémů a jiné oblasti (Fermatovy věty, Gaussova theorie tříd rovnic, Polyova enumerace, Sylowovy grupy,..).
Uvažujme uspořádání n prvků do k buněk. Nechť A je množina s n členy (prvky) a množina E(A) = {0, 1, .., n-1} báze množiny A. Nechť B je množina s k členy (buňkami) a ξ relace z E(B) do E(A).
ξ
(buňky) E(B) ------------- E(A) (prvky)
Nechť čísla E(B) jsou pozice čísel (číslic) z E(A). Přepisem do n-kové
soustavy získáme n^k možných čísel. Označme množinu všech těchto čísel be
M()=M(n,k). Členy této množiny jsou tzv. instance.
Např. množiny A={p, q}, B={x, y, z} mají báze E(A)={0, 1}, E(B)={0, 1, 2}.
Systém M(2,3) má 2^3=8 instancí {000, 001,.., 111}.
Množinu M()=M(n,k) (s relací ξ) budeme nazývat systém stupně n a řádu k.
Jestliže ξ je relace ekvivalence, je možné rozlišit druhy instancí. Druhy jsou
výsledkem rozkladu M()/ξ. Každý druh má své reprezentanty. Počet transpozic
znamená počet členů druhu.
V případě 12-ti tónového temperovaného hudebního systému máme n=2, k=12.
Např. nechť A={existuje, neexistuje} a B={c, c#, d, d#, e, f, f#, g, g#, a, a#,
h}. Báze E(A)={0,1}, E(B)={0, 1, .., 11} a relace ξ utvářejí system M(2,12).
Instance 001001001001 representuje tónové uskupení [c, d#, f#, a] a má dvě
transpozice 010010010010, tj. [c#, e, g, a#] a 100100100100 tj. [d, f, g#, h].
Zmenšený septimový akord je druh z M(2,12) s 3-mi transpozicemi.
Budiž relace G, definována následovně, nazývána G-relace.
u(i,j) = n^j * g(i) ( mod(r-1))
Číslo r je (v tomto článku) vždy předpokládáno rovné celkovému počtu instancí, tj. r = n^k. Číslo g(i) is číslo reprezentanta, u(i,j) jsou čísla instancí.
Systemy s G-relací nazýváme G-systemy, G()=G(n,k). Každý G(n,k) má m(n,k) druhů označených g(i), i=1..m.
Zapišme přehled všech instancí uspořádaný podle druhů. Přehled pro G(n,k) má k sloupců (k je nejvyšší možný počet transpozic). 16 instancí z G(2,4) vytváří 6 druhů.
Instance G(2,4)
1/ 0 0 0000 0
0 0
2/ 0 0 0 1 1 0 0 0 0001 0010 0100 1000 1 2 4 8
0 1 0 0 0 0 1 0
3/ 0 1 1 1 1 0 0 0 0011 0110 1100 1001 3 6 12 9
0 1 0 0 1 0 1 1
4/ 1 0 0 1 0101 1010 5 10
0 1 1 0
5 1 1 1 1 1 0 0 1 0111 1110 1101 1011 7 14 13 11
0 1 1 0 1 1 1 1
6/ 1 1 1111 15
1 1
Algoritmus je podobný Eratosthenovu sítu pro vyčlenění prvočísel z přirozených čísel. V našem případě vyčleňujeme čísla representantů druhů z čísel všech instancí. Transpozice instancí jsou analogie prvočíselných násobků v Eratosthenově sítu.
vyprázdni množinu M
|
+--+- pro g=0 až (n^(k-1)-1) -- zapiš poslední druh
| | | g=n^k-1
| ^ je druh g v M ?
| | |
| +- YES-----+
| |NO
| |
| zapiš g do M
| |
| instance u <- g
| |
|+---> dokud není u v M ----+
|| | |
|| zapiš u do M |
|| | |
|| transpozice instance |
|| u <- n * u |
|+------<-----+ |
+-------------<-------------+
Příklady výstupu:
G(2,1) G(3,1) G(4,1)
0 0 0
1 1 1
2 2
3
G(2,2) G(3,2) G(4,2)
0 0 0 6 9
1 2 1 3 1 4 7 13
3 2 6 2 8 10
4 3 12 11 14
5 7 5 15
8
G(2,3) G(3,3) G(4,3)
0 0 0 21
1 2 4 1 3 9 1 4 16 22 25 37
3 6 5 2 6 18 2 8 32 23 29 53
7 4 12 10 3 12 48 26 41 38
5 15 19 5 20 17 27 45 54
7 21 11 6 24 33 30 57 39
8 24 20 7 28 49 31 61 55
13 9 36 18 42
14 16 22 10 40 34 43 46 58
17 25 23 11 44 50 47 62 59
26 13 52 19 63
14 56 35
15 60 51
Číslo instance u(i,j) je relativním prvočíslem s r -1 = n^k -1 jen když
odpovídající číslo druhu g(i) je relativním prvočíslem s r -1. Počet všech
instancí, která jsou relativními prvočísly s r -1 je φ(r), kde φ je Eulerova
funkce. Jestliže g(i) relativním prvočíslem s r -1, pak jeho druh musí být
vlastní (ne vnořený) a takový druh má k instancí.
Proto: φ(n^k -1)= 0 (mod k)
V G(2,4) jen tyto instance jsou relativní prvočísla s 2^4 -1=15: (1, 2, 4,
8) a (7, 14, 13, 11). A φ(2^4 -1) = φ(15) = 8; 8 = 0 (mod 4).
více
Jedno z prvních řešení problému, který studujeme, bylo publikováno Gaussem v jeho algebraické theorii tříd rovnic [Gauss,1959]. Polya předvedl obecné kombinatorické řešení pro počítání struktur. Jeho enumerační věta [Preparata,1974] byla navržena pro počítání tříd s ohledem na libovolné operace symmetrie. Akordické hudební struktury mají jen jednu takovou operaci - rotaci. Tento fakt nám umožňuje použít jednoduchý algoritmus.
Pro každé d|k existuje system G(n,d) vnořený do G(n,k). Vnořený druh g' v
G(n,k) je podobný svému výchozímu druhu g z G(n,d). Skutečně původní druhy jsou
nazývány vlastní druhy. Podobnost s výchozími druhy znamená týž počet
transpozic a podobné instanční struktury. System G(n,p), p je prvočíslo, má
právě jeden vnořený system G(n,1). Pro g z G(n,d), g' z G(n,k), d|k platí: g' =
c . g kde c ke keficient vnoření definovaný následovně:
c(d,k) = (n^k-1) / (n^d-1). Např. systém G(2,6) získává (dědí) vnořené
systémy G(2,1), G(2,2) a G(2,3);
G(2,1) je také vnořený do G(2,2) a G(2,3).
Jiný příklad: systém G(2,4) dědí vnořené systémy G(2,1) a G(2,2); viz např. druh g(2) = 1 v G(2,2) a jí odpovídající druh g(4) = 5 v G(2,4) s koeficientem vnoření c(2,4) = 5.
G(2,1):
g(1)= u(0,1)= 0
g(2)= u(0,2)= 1
G(2,2):
g(1)= u(0,1)= 0
g(2)= u(0,2)= 1 u(1,2)= 2
g(3)= u(0,3)= 3
G(2,4):
g(1)= u(0,1)= 0
g(2)= u(0,2)= 1 u(1,2)= 2 u(2,2)= 4 u(3,2)= 8
g(3)= u(0,3)= 3 u(1,3)= 6 u(2,3)=12 u(3,3)= 9
g(4)= u(0,4)= 5 u(1,4)=10
g(5)= u(0,5)= 7 u(1,5)=14 u(2,5)=13 u(3,5)=11
g(6)= u(0,6)=15
Koeficienty vnoření:
G(2,1) - G(2,2): c(1,2) = (2^2 -1) / (2^1 -1) = 3
G(2,2) - G(2,4): c(2,4) = (2^4 -1) / (2^2 -1) = 5
Nechť v(n,k), w(n,k) a m(n,k) jsou počty vlastních, vnořených a všech druhů
v G(n,k). Platí:
Specielně pro prvočíslo p je:
Např. System G(2,6) má 14 druhů (9 vlastních + 5 vnořených):
Počítání druhů v G(2,6)
|
Vlastní druhy |
Vnořené druhy |
|
v(2,1)=2/1=2 |
w(2,1) = 0 |
|
v(2,2)=(2^2-1v(2,1))/2= 1 |
w(2,2) = v(2,1) = 2 |
|
v(2,3)=(2^3-1v(2,1))/3= 2 |
w(2,3) = v(2,1) = 2 |
|
v(2,6)=(2^6-1v(2,1)-2*v(2,2)-3*v(2,3))/6 = 9 |
w(2,6) = v(2,1)+v(2,2)+v(2,3)= 5 |
Proto m(2,6)= v(6) +w(6) = 9 +5 = 14 druhů.
Gauss [CG1} předložil předchozí rekurentní rovnice v elegantním, kompaktním tvaru: n^k = ∑d(d) tj. v naší terminologii: n^k = ∑{d|k} d*v(n,d).
Vyčísleme součty všech druhů m(n,k) pro jednotlivé řády k jako funkce n:
k=1: m(n,1)= 1/1 (n) + 0 = n
k=2: m(n,2)= 1/2 (n^2- n)+ n = 1/2 (n^2+n)
k=3: m(n,3)= 1/3 (n^3-n)+ n = 1/3 (n^3+ 2n)
k=4: m(n,4)= 1/4 (n^4-n2)+ 1/2 (n^2+n) = 1/4 (n^4+ n^2+2n)
k=5: m(n,5)= 1/5 (n^5-n) + n = 1/5 (n^5+ 4n)
k=6: m(n,6)= 1/6 (n^6-n^3-n^2+n)+1/6(2n^3+3n^2+n)= 1/6 (n^6+n^3+2n^2+2n)
k=7: m(n,7)= 1/7 (n^7-n) + n = 1/7 (n^7+ 6n)
k=8: m(n,8)= 1/8 (n^8-n^4)+ 1/4(n^4+n^2+2n)=1/8(n^8+n^4+2n^2+4n)
V případě rotačních operací dává Polyova teorie tento výsledek [Beckenbach,1964]:
m(n,k) = 1/k ∑{d|k} φ(d)* n^{k/d} (včetně d=k),
kde φ je Eulerova funkce.
Vnořování (ukázané v předchozích odstavcích) je záležitostí G-systemů s
konstantním n.
Nyní budeme vyšetřovat G-systemy s konstantním k. Tyto systémy také mají něco
společného.
Např. podívejme se na systémy G(2,2) a G(3,2). Druhý je jen rozšířením prvního.
G(3,2) jako rozšíření G(2,2)
G(2,2) = G(3,2) 0 0 1 2 1 3 3 4 6 2 7 5 8 |
Každý G(n,k) má n druhů vnořených z G(n,1). Předpokládejme, tyto druhy
rozdělují G-system do segmentů. Nechť s (s
g(s) = (n-s) * (n^k-1) / (n-1).
Jestliže nějaký segment existuje v G(n,k), pak podobný segment existuje také v
G(n+1,k). Tato myšlenka se objasní, když přepíšeme všechna čísla u čísly
(n^k-1)-u.
Segmentace G(3,3)
u 0 segment 2 1 3 9 2 6 18 4 12 10 5 15 19 7 21 11 8 24 20 ------------------ 13 segment 1 14 16 22 17 25 23 ------------------ 26 segment 0 |
(n^k-1)-u = 27-u 0 segment 0 ------------------ 9 1 3 12 10 4 13 segment 1 ------------------ 18 2 6 19 5 15 21 11 7 22 14 16 24 20 8 25 23 17 26 segment 2 |
Zapišme čísla n^k-1-u z předchozí tabulky jako funkce n a podívejme se na koeficienty polynomů:
k=2 k=3
segment 0 segment 0
1 1
segment 1 segment 1
n 1 n^2 1 n
n+1 n^2+n n^2+1 n +1
n^2+n+1
Koeficienty těchto polynomů jsou:
k=2 k=3
segment 0 segment 0
0 0 0 0 0
segment 1 segment 1
1 0 0 1 1 0 0 0 0 1 0 1 0
1 1 1 1 0 1 0 1 0 1 1
1 1 1
Každý G-system je množinou čísel z n-kové číselné soustavy. G-relace rozděluje G(n,k) do n segmentů, kde každý segment s užívá právě s symbolů, s=0..n-1.
Skladba G-systemů
G(1,2) 00 00 00 ---------------------------- 10 01 10 01 10 01 G(2,2) 11 11 11 ---------------------------- 20 02 20 02 20 02 21 12 21 12 21 12 G(3,2) 22 22 22 ---------------------------- 30 03 30 03 31 13 31 13 32 23 32 23 G(4,2) 33 33 ---------------------------- 40 04 41 14 42 24 43 34 G(5,2) 44 ---------------------------- |
G(1,3) 000 000 000 -------------------------------------------- 100 001 010 100 001 010 100 001 010 110 101 011 110 101 011 110 101 011 G(2,3) 111 111 111 -------------------------------------------- 200 002 020 200 002 020 201 012 120 201 012 120 210 102 021 210 102 021 211 112 121 211 112 121 220 202 022 220 202 022 221 212 122 221 212 122 G(3,3) 222 222 -------------------------------------------- 300 003 030 301 013 031 302 023 032 310 103 130 311 113 131 312 123 132 320 203 230 321 213 231 322 223 232 330 303 330 331 313 331 332 323 332 G(4,3) 333 -------------------------------------------- |
Součet polynomických koeficientů je stejný pro všechny instance daného druhu (instance téhož druhu mají stejnou úroveň).
Binarní systém G(2,k) is zvláštní případ G-systemu, n=2. Je vhodný pro klassifikaci hudebních struktur.
V binarním systému (base E(A) ={0, 1}) je snadné vyjádřit strukturu
instancí.
Nechť úroveň druhu L je počet číslic "1" v instanci a nechť interval
je vzdálenost mezi dvěma číslicemi "1". Distanční schéma je výpis
všech sousedících intervalů, poslední interval v závorkách, [Janecek,1959].
Distanční schéma instancí v G(2,4))
i g(i) Instance čísla (binary) Schema Level ------------------------------------------------------ 1 0 0000 (0) 0 2 1 0001 0010 0100 1000 (4) 1 3 3 0011 0110 1100 1001 1(3) 2 4 5 0101 1010 2(2) 2 5 7 0111 1110 1101 1011 1 1(2) 3 6 15 1111 1 1 1 (1) 4 |
Poslední sloupec předchozí tabulky zobrazuje úroveň odpovídajícího druhu, tj. úroveň instancí druhu. Spočítejme kolik instancí a druhů je na každé úrovni.
Počítání v G(2,4)
Úroveň 0 1 2 3 4 -------------------------------------------- Všechny instance 1 4 6 4 1 Vnořené instance 1 0 2 0 1 Vlastní instance 0 4 4 4 0 -------------------------------------------- Všechny druhy 1 1 2 1 1 Vnořené druhy 1 0 1 0 1 Vlastní druhy 0 1 1 1 0 |
Následující schemata zobrazují totéž (strukturováno do trojúhelníků) pro
všechna G(2,k). První sloupec zobrazuje řád k daného G-systemu, v dalších
sloupcích jsou počty pro jednotlivé úrovně. Poslední sloupce obsahují součty
instancí a druhů. Trojúhelníky jsou symmetrické, zapisujeme jen jejich
polovinu.
Např. v 12-ti tónové hudbě je 220 trojzvuků, 19-ti druhů. Těchto 19 druhů
znamená, že existuje 19 typů trojzvuků (moll, dur, zvětšený, zmenšený, ...).
Jeden jediný druh (zvětšený trojzvuk) je vnořený. Tento druh má 4 instance.
Proto je 220-4=216 vlastních instancí trojzvuků a 216/12 = 19-1 = 18 vlastních
druhů trojzvuků.
k (0)(1)(2)(3) (4) (5) (6) (7) (8) (9)(10)(11)(12)
----------------------------------------------------------------------
12 1 12 66 220 495 792 924 792 495 220 66 12 1 všechny instance
----------------------------------------------------------------------
1 1 1
2 0 2 0
3 0 3 3 0 vnořené instance
4 0 4 4 4 0
6 0 6 12 18 12 6 0
----------------------------------------------------------------------
12 0 12 60 216 480 792 900 792 480 216 60 12 0 vlastní instance
12 0 1 5 18 40 66 75 66 40 18 5 1 0 vlastní druhy
----------------------------------------------------------------------
1 1 1
2 0 1 0
3 0 1 1 0 vnořené druhy
4 0 1 1 1 0
6 0 1 2 3 2 1 0
----------------------------------------------------------------------
12 1 1 6 19 43 66 80 66 43 19 6 1 1 všechny druhy
Trojúhelník vlastních instancí a vlastních druhů
|
|
|
Trojúhelník vnořených instancí a vnořených druhů
|
|
|
Trojúhelník všech instancí (Pascalův) a všech druhů
|
|
|
Celkový počet vnořených instancí stejně tak jako vnořených druhů v systému s
prvočíselným k je roven 2. Počet vlastních instancí je vždy k-násobkem počtu
vlastních druhů.
více
V článku byl představen náhled do problému hudebních structur. Výsledky byly
porovnány s podobnými výsledky získanými Gaussem a Polyou. Teorie G-systémů má
také vazby do jiných matematických oblastí.
Např. omezení systemů (r<n^k)
vede k teorii primitivních kořenů; rozložení prvočísel v
jednotlivých druzích by mohlo poskytnout nějaké informace o prvočíslech;...
Zvláště trojúhelník
vlastních druhů by mohl být zajímavý. S jeho strukturou jsou spojeny
některé věty o prvočíslech (Wilsonova věta,...). Trojúhelník se zdá být
obecnější než Pascalův trojúhelník - Pascalův může být získán integrací jeho
členů.
Teorie byla prezentována v poster-sekci Conference on Computational and
Mathematical Methods in Music, ve Vídni, 1.-4.prosince 1999 (Diderot Forum on
Mathematics and Music). Text, jenž následuje, pokrývá a rozšiřuje text otištěný
ve sborníku konference.
Na začátku jsem nazýval tyto systémy pojmem "Genetické systémy", pro
jistou analogii s dědičností (viz Vnořování G-systemů). Později jsem jméno
zkrátil na "G-systemy". Na teorii jsem pracoval převážně v letech
1990-1992. V letech následujících, 1993-1996, pak hledal podobné teorie v
literatuře.
Enumerace celkového počtu druhů v G-systemu je shodná s enumerací celkového
počtu tříd rovnic, která byla studována Carl Fridrichem Gaussem zhruba před 200
lety. Takže písmeno G ve jménu "G-system" by mohlo být spojeno s
Gauss. Byl pravděpodobně první, kdo znal a popsal tyto matematické konstrukce.
Gauss,1959 Gauss Carl Fridrich: Trudy po teorii cisel (Ucenie o
vycetach II),p.782) (Works on Theory of Numbers; in Russian), Moscow 1959.
Janecek,1959 Janeček Karel: Základy moderní harmonie
(Fundamentals of Modern Harmony; in Czech), Prague 1965.
Beckenbach,1964 Edwin F.Beckenbach, George Polya: Applied
Combinatorial Mathematics University of California, John Wiley and Sons,Inc
, New York, 1964.
Preparata,1974 Franco P.Preparata, Raymond T.Yeh Introduction of
Discrete Structures Addison-Wesley Publishing Company Inc., U.S.A., 1974.
